package com.atguigu.recursion;

public class MiGong {

    public static void main(String[] args) {
        //创建一个二维数组模拟迷宫
        //地图
        //使用1表示墙，最外围为1
        int[][] migong=new int[8][7];
        //设置挡板
        for(int i=0;i<8;i++){
            migong[i][0]=1;
            migong[i][6]=1;
        }
        for(int i=0;i<7;i++){
            migong[0][i]=1;
            migong[7][i]=1;
        }
        migong[3][1]=1;
        migong[3][2]=1;
        //输出地图
        System.out.println("迷宫初始样子");
        for (int i = 0; i < migong.length; i++) {
            for (int j = 0; j < migong[i].length; j++) {
                System.out.print(migong[i][j]+" ");

            }
            System.out.println();

        }
        System.out.println("走迷宫");
        boolean b = setWay(migong, 1, 1);
        System.out.println(b);
        System.out.println("走了之后的样子");
        for (int i = 0; i < migong.length; i++) {
            for (int j = 0; j < migong[i].length; j++) {
                System.out.print(migong[i][j]+" ");

            }
            System.out.println();

        }
    }






    //使用递归回溯给小球找路
    /*
    * map地图
    * i.j表示出发点
    * 如果小球能到6，5，则说明通路找到
    * 当地图的i，j为0时表示该点还没走过，1表示墙，2表示通路3表示该位置已经走过，但是走不通
    * 走迷宫是确定一个策略，先走下-》右-》上-》左
    * 如果该点走不通，回溯
    * */
    public static boolean setWay(int[][] map,int i,int j){
        if(map[6][5]==2){//表示找到了终点
            return true;
        }else{
            if(map[i][j]==0){//该点还没走过
                map[i][j]=2;//表示该点可以走通，但是不一定
                if(setWay(map,i+1,j)){//向下试探，能否走通
                    return true;
                }else if(setWay(map,i,j+1)){//向右试探
                    return true;
                }else if(setWay(map,i-1,j)){//向上试探
                    return true;
                }else if(setWay(map,i,j-1)){//向左试探
                    return true;
                }else{//都走不通
                    map[i][j]=3;
                    return false;
                }
            }else{//表示该点，不行需要倒回去
                return false;
            }
        }
    }

}
